模拟赛题解/2025.10.14 模拟赛

T1-共同好友（A）

题面

社交网络可以看做一张图，每个人为一个结点，如果 $2$ 人互为好友则连一条双向边。

在社交网络应用中，一个常见的问题是询问 $2$ 个人的共同好友数量，请你解决这个问题。

$1\leq n,q\leq10^5,1\leq m\leq10^6,1\leq u,v\leq n$。

题解

本质上就是无向图三元环计数的运用，考虑根号分治，度数 $\geq \sqrt{2m}$ 的数用 bitset 预处理，其他点直接暴力跑。

复杂度为 $O(q(\sqrt{2m}+n/w))$。

T2-操作序列（B）

题面

有 $n$ 个变量 ，初始值都为 0。

依次给出 $m$ 个操作的信息，操作分为 2 种：

• $(1,id,v)$：代表将 $x[id]$ 的值加上 $v$；

• $2$：代表将所有变量的值乘 $2$；

所有运算在 $(\bmod 10^4)$ 下执行。

现在给出一个操作序列，请问依次执行序列中的所有操作之后，每个变量的值是多少。

具体的，操作序列以 $q$ 个区间 $[l_i,r_i]$ 的形式给出，依次执行每个区间、每个区间按编号从小- >大执行区间内的操作，即完整的操作序列为：

• $l_1\sim r_1,l_2\sim r_2,\dots,l_q\sim r_q$。

$1\leq n,m,q\leq2\times10^5,op={1,2},1\leq id\leq n,1\leq v\leq10^9$。

题解

记第 $i$ 个区间的乘法次数之和为 $s_i$。

对于某次加法操作 $p$，其最终贡献取决于它之后的所有乘法操作次数 $cnt$，可以将 看成由 $2$ 部分组成：

1. 对于所有包含 $p$ 的区间 $[l_i,r_i]$，之后所有区间的乘法次数之和 $\sum_i\sum_{j>i}s_j$。
2. 对于所有包含 $p$ 的区间 $[l_i,r_i]$，区间内 $[p+1,r_i]$ 中的乘法次数之和。

从 $q\rightarrow1$ 遍历所有区间，维护一个倒序差分数组 $d$，对于第 $i$ 个区间：

1. 在 $d[r_i]$ 处加上 $2^{\sum_{j>i}s_j}$；
2. 在 $d[l_i-1]$ 处减去 $2^{s_i+\sum_{j>i}s_j}$；

从 $m\rightarrow1$ 遍历所有操作，维护一个变量 $now=2^{cnt}$，由差分数组 $d$ 可以求出第一部分 $\sum_i\sum_{j>i}s_j$；每次遇到乘法操作让 $now$ 乘 $2$ 就可以正确处理第 $2$ 部分区间内的贡献。

复杂度 $O(q+m)$。

T3-AND和XOR（C）

题面

给定 $n$ 个整数 $a[1,2,\dots,n]$，在这 $n$ 个整数中选出 $k$ 个（$k>0$），使得 $k$ 个数的按位 and 和恰好等于按位 xor 和。

$2$ 种方案不同当且仅当选出的 $k$ 个数的下标集合不同，请你求出不同的选择方案数，对 $10^9+7$ 取模。

$1\leq n\leq10^6,0\leq a[i]\leq2^{16}$。

题解

首先有 $O(na^2)$ 的暴力DP，滚动之后空间是 $O(a^2)$，可以得到 $60$ 分。

观察到每位只有3个状态：全为 $1$，或者有奇数/偶数个 $1$。 可以预处理 $s\rightarrow$ 其三进制表示。 记 DP 状态 $f[i][0/1][s]$ 前 $i$ 个数已经选了奇数/偶数个数，每位的状态是 $s$ 的方案数，枚举 $a[i]$ 选或不选进行转移，复杂度 $O(n3^{12})$，滚动之后空间 $O(3^{12})$。

考察我们实际上求了什么：设 $f_{s,j,0/1}$ 表示在所有 $x\&s=s$ 的 $x$ 中选出一个大小为奇数/偶数 的子集，异或和为 $j$ 的方案数，我们最后要求的是 $\sum_s f_{s,s,1}+(-1)^{popcount(s)}(f_{S,0,0}-1)$。

先枚举 $s$，设 $a_1,a_2,\dots,a_k$ 表示所有 $x\&s=s$ 的 $x$ 组成的序列，布尔数组 $c_1,c_2,\dots,c_k$ 表示所有每个 $x$ 有没有被选，发现选奇数/偶数个和异或和的都限制可以被一个异或方程组刻画。

枚举每一位 $h$，设 $x(h)$ 表示 $x$ 的第 $h$ 位，则 $f_{s,s,1}$ 的限制为：

$$\begin{cases} c_1\oplus c_2\oplus \dots\oplus c_k=S\\ a_{1(0)}c_1\oplus a_{2(0)}c_2\oplus \dots\oplus a_{k(0)}c_k=S(0)\\ a_{1(15)}c_1\oplus a_{2(15)}c_2\oplus \dots\oplus a_{k(15)}c_k=S(15) \end{cases}$$

$f_{s,0,0}$ 和其本质相同。 对其做高斯消元，若无解方案数就是 $0$，否则就是 $2^{k-cnt}$， 为消完后的矩阵非 $0$ 行的个数。

直接做是 $O(2^mm^2n)$ 的，期望获得 55 分。

发现由于矩阵只有 $0/1$，所以可以把每行存到一个 bitset 里优化高斯消元，复杂度除以一个 $w$，可以获得 $70-80$ 分不等。

到这时候你会发现你把线性基给忘了，而线性基的经典应用——求 $n$ 个数选出异或和为 $x$ 的子 集的方案数，和上面的高斯消元是等价的。 具体地，我们先把每一个 $a_i$ 增加一个恒为 $1$ 的位，这里使用了 $a_i\times 2+1\rightarrow a_i$，这样如果我们要求选奇数个异或和为 $S$，就变成了选异或和为 $2S+1$ 的子集。于是这个问题就直接可以用线性基解决。

具体地，将修改后的每个 $a_i$ 插入线性基，设 $tot$ 为插入失败的 $a_i$ 个数（即 $a_i$ 能被已经插入的 数表示出来）。则 $f_{s,0,0}=2^{tot}$；若 $2S+1$ 能被表示，$f_{s,s,1}=2^{tot}$，否则为 $0$（简单来说就是 $tot$ 个数可以随便取或不取，最后再用插入成功的那些数唯一地组合出 $2S+1$），具体证明可 以自行上网查找。 复杂度 $O(2^mnm)$，期望获得 80 分。

每次枚举 $S$ 挨个加入每个数太蠢了，考虑 $S$ 的线性基里面是 $S$ 的超集形成的线性基，所以我们直接可以用类似高维前缀和的方式进行 $O(2^mm)$ 次合并，每次合并是 $O(m^2)$ 的，所以加上每个值插入的复杂度，总复杂度是 $O(nm+2^mm^3)$，常数很小。

T4-朝日（D）

题面

定义素数导出序列为一个序列 $T$，其中每个元素都是素数，且单调不降。

若把所有素数导出序列，按照序列中元素和作为第一关键字，序列中元素个数作为第二关键字, 序列的字典序作为第三关键字排序。将所有素数导出序列从小到大排序后取前 $10^{21}$ 个序列组成 的数组,每个序列是一个 vector，所有序列按照顺序放进一个 vector 里面，输出这样一个 C++ 源码可以用于打表。

现在请你输出这个表的第 $l$ 个字符到第 $r$ 个字符。

$1\leq l\leq r\leq10^{18},r-l+1\leq10^7+5$。

题解

考虑令 $f[i,j,k]$ 为第 $i$ 个素数以后构成的、序列和为 $j$、长度为 $k$ 的素数导出序列个数。

$g_[[i,j,k]]$ 为第 $i$ 个素数以后构成的、序列和为 $j$ 、长度为 $k$ 的素数导出序列对应的字符串的总长度。

显然我们可以递推 ，这是一个基础背包。 考虑复杂度，根据计算发现，第 $10^{18}$ 个字符大约是在和 $735$ 的时候取到，所以总状态数有 $\pi(s)s^2/2\approx3.5\times10^7$ 个，可以通过。

那么我们每次想知道一个字符，只需要像 50分一样，大力 DFS，根据 $f,g$ 判断下面的分支的大 小，进入适当的分支，就可以了。